package com.test.daily.leetcode.y2022.m07.day0707.v04;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/12 下午 03:04
 * @version: 1.0
 */
public class Solution {
    public static int countOfRange(int[] arr, int a, int b){
        int[] sum = new int[arr.length];
        sum[0] = arr[0];
        for(int i = 1; i < sum.length; i++){
            sum[i] = arr[i] + sum[i-1];
        }
        return process(sum, 0, arr.length-1, a, b);
    }
    public static int process(int[] arr, int left, int right, int a, int b) {
        int mid = left + ((right - left) >> 1);
        return process(arr, left, mid, a, b)
                + process(arr, mid + 1, right, a, b)
                + merge(arr, left, mid, right, a, b);
    }

    public static int merge(int[] arr, int left, int mid, int right, int lower, int upper) {

        int[] help = new int[right - left + 1];
        int p1 = left, p2 = mid + 1;
        int i = 0;
        int ans = 0;
        int windowsL = left;
        int windowsR = right;
        for(int j = mid + 1; j <= right; j++){
            int min = arr[j] - upper;
            int max = arr[j] - lower;
            while(windowsR <= mid && arr[windowsR] <= max){
                windowsR++;
            }
            while(windowsL<= mid && arr[windowsL] < min){
                windowsL++;
            }
            ans += windowsR - windowsL;
        }

        while(p1 <= mid && p2 <= right){
            help[i++] = arr[p1] < arr[p2] ? arr[p1++]: arr[p2++];
        }
        while(p1<=mid){
            help[i++] = arr[p1++];
        }
        while(p2<=right){
            help[i++] = arr[p2++];
        }
        i = 0;
        for(;i < help.length; i++){
            arr[left + i] = help[i];
        }
        return ans;
    }
}
